/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package commonlib.domain;

/**
 *
 * @author jorge.daniel.negrete
 */
import java.util.ArrayList;
import java.util.Iterator;



public class TST<T>  {
	protected Node<T> node;
	private IteratorTST<T> I;
	private int cont_p;
	public TST()
	  {
		this.node=null;
		cont_p=0;
	  }
	public TST(TST<T> tst)
	{
		this.node=tst.node;
	}

	public T getDade(String p)
	{
		return this.trobar_dade_recursiva(p,0, this.iterator());
	}

	private T trobar_dade_recursiva(String p,int cont,IteratorTST<T> i)
	{
		Node<T> aux;
	    boolean encontrado;
	    while(i.hasNext()!=0)
	    {
	    	aux=i.next();
	    	encontrado=false;
	    	while(!encontrado)
	    	{
	    		if(aux.getLetter()==p.charAt(cont))
	    		{
	    			if(p.length()-1==cont)
	    			{
	    				return aux.getData();
	    			}
	    			else if(aux.getMiddle()!=null)
	    			    {
	    			  	encontrado=true;
	    				cont++;
	    			    }
	    		     	else
	    			   {
	    			     return null;
	    		     	}
	    		}
	    		else
	    		{
	    		  if(i.hasNextBro())
	    		  {
	    			  aux=i.nextBro();
	    		  }
	    		  else
	    		  {
	    			  return null;
	    		  }
	    		}
	    	}
	    }
	    return null;
    }

   public void setDade(String p,T dade)
	{
	   this.afegir_recursivo(p, 0,this.node,dade,1);
	}

  private boolean trobar_paraula_iterativo(String p,int cont,IteratorTST<T> i)
	  {
	    Node<T> aux;
	    boolean encontrado;
	    while(i.hasNext()!=0)
	    {
	    	aux=i.next();
	    	encontrado=false;
	    	while(!encontrado)
	    	{
	    		if(aux.getLetter()==p.charAt(cont))
	    		{
	    			if(p.length()-1==cont)
	    			{
	    				return aux.getMarked();
	    			}
	    			else if(aux.getMiddle()!=null)
	    			    {
	    			  	encontrado=true;
	    				cont++;
	    			    }
	    		     	else
	    			   {
	    			     return false;
	    		     	}
	    		}
	    		else
	    		{
	    		  if(i.hasNextBro())
	    		  {
	    			  aux=i.nextBro();
	    		  }
	    		  else
	    		  {
	    			  return false;
	    		  }
	    		}
	    	}
	    }
	    return false;
	  }
	private Node<T> afegir_recursivo(String s,int pos,Node<T> t,T dades,int nivel)
	  {
		if(t==null)
	  	{
	  		t=new Node<T>(s.charAt(pos),false,null,nivel);
	  	}
	  	if(s.charAt(pos)<t.getLetter())
	  	{
	  		t.setLeft(afegir_recursivo(s,pos,t.getLeft(),dades,nivel));
	  	}
	  	else if(s.charAt(pos)>t.getLetter())
	  	{
	  		t.setRight(afegir_recursivo(s,pos,t.getRight(),dades,nivel));
	  	}
	  	else{
	  		if((pos+1)==s.length())
	  		{
	  			t.setMarked(true);
	  			t.setData(dades);

	  		}
	  		else
	  		{
	  			t.setMiddle(afegir_recursivo(s,pos+1,t.getMiddle(),dades,nivel+1));
	  		}
	  	}
	  	return t;
	  }

	public void add(String paraula)
	{
		node=this.afegir_recursivo(paraula,0,this.node,null,1);
		cont_p=cont_p+1;
	}
	public void add(String paraula,T dade)
	{
		node=this.afegir_recursivo(paraula,0,this.node,dade,1);
	}
	public boolean contains(String paraula)
	{
		if(this.node!=null)
		{
			return this.trobar_paraula_iterativo(paraula,0, this.iterator());
		}
		else
		{
			return false;
		}

	}
    protected boolean delete(String A)
    {
    	if(this.contains(A))
    	{
      		this.node=Eliminar_Paraula_recusivo(A,0,node);
    		return true;
    	}
    	else
    	{
    		return false;
    	}

    }
    private Node<T> Eliminar_Paraula_recusivo(String A,int pos,Node<T> n)
    {
    	if(A.charAt(pos)==n.getLetter())
    	{
    		if(A.length()-1==pos)
    		{
    			n.setMarked(false);
    			n.setData(null);
    			if(n.getMiddle()==null)
   		      	 {
   				 n=unir(n.getRight(),n.getLeft());
   			     }
    		}
    		else
    		{
    			 n.setMiddle(this.Eliminar_Paraula_recusivo(A,pos+1,n.getMiddle()));
    			 if((n.getMiddle()==null)&&(!n.getMarked()))
    			 {
    				 n=unir(n.getRight(),n.getLeft());
    			 }

    		}
    	}
    	else if(A.charAt(pos)>n.getLetter())
    	{
    		 n.setRight(this.Eliminar_Paraula_recusivo(A,pos,n.getRight()));
    	}
    	else
    	{
    		 n.setLeft(this.Eliminar_Paraula_recusivo(A,pos,n.getLeft()));
    	}
    	return n;
    }

	public IteratorTST<T> iterator()
	 {
			I=new IteratorTST<T>(this.node);
			return I;
     }
	public void clear()
	{
		this.node=null;
		cont_p=0;
	}

	public boolean	isEmpty()
	{
	   	if(cont_p==0)
	   	{
	      return true;
	   	}
	   	else
	   	{
	   		return false;
	   	}
    }
	public void addAll(ArrayList<String> p)
	{
	  Iterator<String>aux=p.iterator();
	  while(aux.hasNext())
	  {
		  this.add(aux.next());
	  }
	}
	private Node<T> unir(Node<T> derecho,Node<T> izquierdo)
	{
		if(derecho==null)
		{
		  return izquierdo;
		}
		else if(izquierdo==null)
		{
	      return derecho;
		}
		else
		{
			Node<T> centro=unir(izquierdo.getRight(),derecho.getLeft());
			izquierdo.setRight(centro);
			derecho.setLeft(izquierdo);
			return derecho;
		}
	}
}